In the world of postal delivery, when a registered letter arrives, a person officially receives the letter if and only if that person signs an acknowledgement that attests to receipt of the letter. In this example, two actions (i.e., signing an acknowledgement and receiving the letter) occur simultaneously. In an electronically connected world, electronic mail (i.e., “emails”) are used widely. Most people prefer email to snail mail when communicating with others due to convenience and fast delivery, as well as documentation (e.g., a sent items box). To place email on par with conventional postal delivery, an email system should include some type of function that provides the same assurance as a registered letter. In particular, such a function should require a receiver of an email to sign an acknowledgement of reception before the registered email can be read.
In contrast to the world of postal delivery for registered letters, for an email system, the two actions, i.e., signing and receiving, cannot occur simultaneously due to the email system's distributed nature: protocols used in an email system are asynchronous by nature.
Some services exist that can provide a “registered letter” in a distributed environment. For example, a so-called certified email protocol, also known as the non-repudiation protocol can provide for a fair exchange of a message and an undeniable receipt between two untrusted parties over a network such as the Internet.
In addition to certified emails, a certified email protocol can also be used in many other applications. One application is to secure an itinerary of a mobile agent, where a certified email protocol is applied between two adjacent hosts when a mobile agent passes from one host to the other. In this context, the non-deniable message and receipt offered by a certified email protocol can be used to identify the origin of an attack if the itinerary of the mobile agent is altered. Other applications that can benefit from a certified transaction protocol include applications that encourage people to share or propagate contents such as self-created movies or advertisements, where a certified email protocol can help assure that users who share content get awards by redeeming the receipts from those that receive the content.
Certified email protocols have been studied widely by the cryptography research community. Certified email protocols address a problem that is essentially a subset of a problem addressed by the so-called “fair exchange protocol”, where exchanged items are not necessarily restricted to messages and receipts as in certified email protocols (i.e., digital items other than emails can be exchanged using the fair exchange protocol). For example, both parties can exchange signatures signed by each individual party in a fair exchange protocol.
Depending on the availability and setting of a Trusted Third Party (TTP), fair exchanges can be classified into the following four types: (1) without a TTP, (2) with an inline TTP, (3) with an online TTP, and (4) with an off-line TTP. For the first type of fair exchanges, as early as in 1980, studies showed that it is impossible to realize fairness in a deterministic two-party fair exchange protocol. Existing protocols can provide only partial fairness: computational fairness or probabilistic fairness. Such protocols, however, tend to be too complex and inefficient to be applied in practical applications (e.g., distributed Web-based applications). For the second type of fair exchanges, the TTP acts as an intermediary between the sender and the receiver, and the entire message is sent through the TTP. An inline TTP can provide full fairness since all exchanged messages are fully controlled by the TTP. The TTP, however, may become a performance bottleneck, especially when many large messages have to be forwarded at the same time. For the third type, an online TTP, which is similar to an inline TTP, must be available for the entire lifetime of the exchange. In such a setting, the TTP does not need to forward the entire message. Only the signaling information such as the cryptographic key is processed and forwarded by the TTP. For the last type of fair exchanges, also known as the optimistic protocol, the TTP is involved only if one of the parties behaves maliciously or the communication channel is interrupted during execution of the exchange protocol. This property is practical in many applications, including the distributed environment mentioned above (e.g., distributed Web-based environment).
Aside from specific certified email protocols, various generic certified email protocols exist, where generic encryption and signature primitives are used. Such generic certified email protocols usually utilize the following approach: (i) encrypting a message by a symmetric encryption scheme, (ii) encrypting the key used in the symmetric encryption by a public key encryption scheme with the TTP's public key, and (iii) signing the resulting cipher text by a signature scheme with the sender's private key. In such a scheme, when the receiver receives the signature, the receiver first checks validity of the received signature. If it is valid, the receiver sends a receipt to the sender to indicate that the receiver has received the message. The receiver's interest is protected since if the sender refuses to reveal the exchanged message, the TTP can reveal the message for the receiver.
Overall, the off-line TTP approach has advantages yet, to date, off-line TTP certified email protocols lack efficiency. As described herein, various exemplary techniques can improve efficiency of off-line TTP certification protocols. Such techniques may be implemented in the context of email and/or other transactions that occur in a distributed environment.